|
In graph theory, a branch of mathematics, Halin's grid theorem states that the infinite graphs with thick ends are exactly the graphs containing subdivisions of the hexagonal tiling of the plane. It was published by , and is a precursor to the work of Robertson and Seymour linking treewidth to large grid minors, which became an important component of the algorithmic theory of bidimensionality. ==Definitions and statement== A ray, in an infinite graph, is a semi-infinite path: a connected infinite subgraph in which one vertex has degree one and the rest have degree two. defined two rays ''r''0 and ''r''1 to be equivalent if there exists a ray ''r''2 that includes infinitely many vertices from each of them. This is an equivalence relation, and its equivalence classes (sets of mutually equivalent rays) are called the ends of the graph. defined a thick end of a graph to be an end that contains infinitely many rays that are pairwise disjoint from each other. An example of a graph with a thick end is provided by the hexagonal tiling of the Euclidean plane. Its vertices and edges form an infinite cubic planar graph, which contains many rays. For example, some of its rays form Hamiltonian paths that spiral out from a central starting vertex and cover all the vertices of the graph. One of these spiraling rays can be used as the ray ''r''2 in the definition of equivalence of rays (no matter what rays ''r''0 and ''r''1 are given), showing that every two rays are equivalent and that this graph has a single end. There also exist infinite sets of rays that are all disjoint from each other, for instance the sets of rays that use only two of the six directions that a path can follow within the tiling. Because it has infinitely many pairwise disjoint rays, all equivalent to each other, this graph has a thick end. Halin's theorem states that this example is universal: every graph with a thick end contains as a subgraph either this graph itself, or a graph formed from it by modifying it in simple ways, by subdividing some of its edges into finite paths. The subgraph of this form can be chosen so that its rays belong to the given thick end. Conversely, whenever an infinite graph contains a subdivision of the hexagonal tiling, it must have a thick end, namely the end that contains all of the rays that are subgraphs of this subdivision.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Halin's grid theorem」の詳細全文を読む スポンサード リンク
|